package com.yoshino.leetcode.interview150.array;

import java.util.*;

class RandomizedSet {

    Random random = new Random();
    Map<Integer, Integer> map;
    List<Integer> list;

    public RandomizedSet() {
        // 随机访问
        list = new ArrayList<>();
        // 插入O(1)
        map = new HashMap<>();
    }
    
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        // 优化
//        Integer remove = map.remove(val);
//        list.remove(remove);
        int last = list.get(list.size() - 1);
        if (val != last) {
            // 将需要删除的移到最后
            Integer cur = map.get(val);
            map.put(last, cur);
            list.set(cur, last);
        }
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }
    
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */